11 Fast Fourier Transform
梦里不觉秋已深，余情岂是为他人。
章节目录
- 章节目录
- 11-1 DFT 计算问题 DFT Computation Problem
- 11-2 旋转因子 Twiddle Factor
- 11-3 Cooley-Tukey 算法 Cooley-Tukey FFT
- 11-4 按时间抽取 FFT DIT FFT
- 11-5 按频率抽取 FFT DIF FFT
- 11-6 用 FFT 计算 IDFT IDFT Using FFT
- 11-7 MATLAB 中的 DFT/IDFT MATLAB DFT and IDFT
- 11-8 位反转地址 Bit-Reversed Addressing
11-1 DFT 计算问题 DFT Computation Problem
11-1-1 直接计算 Direct Computation
回顾第 5 章的 DFT 约定：
其中：
若直接计算全部
因此直接 DFT 的复数运算量为：
| 计算项 Computation Item | 运算量 Count |
|---|---|
| 复数乘法 Complex Multiplication | |
| 复数加法 Complex Addition |
当
11-1-2 FFT 的位置 Role of FFT
快速傅里叶变换 Fast Fourier Transform, FFT 是 DFT 的快速计算算法，变换定义仍然是 DFT。
本章只讨论最常用的 radix-2 FFT。设序列长度为：
FFT 的计算目标是把一个
11-2 旋转因子 Twiddle Factor
11-2-1 定义 Definition
DFT 中的复指数因子称为旋转因子 Twiddle Factor：
它在复平面单位圆上取值。FFT 能够减少计算量，主要依赖旋转因子的周期性和对称性。
11-2-2 基本性质 Basic Properties
1. 周期性 Periodicity
因此：
频率索引和时间索引都只需要在长度
2. 共轭对称 Conjugate Symmetry
并且：
3. 降阶关系 Reduction
若
当
特别地：
这是 radix-2 FFT 推导中最常用的一步。
4. 半周期符号 Half-Period Sign
当
于是：
这个性质使上半频点和下半频点可以共用同一组较短 DFT 结果。
11-3 Cooley-Tukey 算法 Cooley-Tukey FFT
11-3-1 分解思想 Decomposition Idea
Cooley-Tukey FFT 的基本思路是把一个长 DFT 分解成若干短 DFT，再用旋转因子把这些短 DFT 合成。
以 radix-2 为例：
每一层分解只改变数据的组合方式，不改变 DFT 的定义。
11-3-2 计算量 Complexity
radix-2 FFT 一共有：
级。每一级包含
按一般复数乘法计数，全部
与直接 DFT 对比：
| 点数 | 直接乘法 | 直接加法 | radix-2 FFT 乘法 | radix-2 FFT 加法 |
|---|---|---|---|---|
实际实现中，
11-4 按时间抽取 FFT DIT FFT
11-4-1 偶奇抽取 Even-Odd Decimation
按时间抽取 Decimation-in-Time, DIT 先在时域把输入序列分成偶序号和奇序号两部分：
将它们代入 DFT 定义：
定义两个
于是：
其中
11-4-2 蝶形计算 Butterfly Computation
利用
由此得到 DIT 的基本蝶形：
每个蝶形把两个较短 DFT 的同序号输出合成两个较长 DFT 的输出。
DIT 的典型特征：
- 输入按时间索引不断偶奇抽取；
- 输出可以保持自然顺序；
- 若采用原地计算，输入通常需要先排成位反转顺序。
11-5 按频率抽取 FFT DIF FFT
11-5-1 频域抽取 Frequency Decimation
按频率抽取 Decimation-in-Frequency, DIF 从输出频点的偶数项和奇数项出发。
先把输入序列按前后两半分组：
当
当
定义：
则有：
DIF 的蝶形先做加减，再把差值支路乘以旋转因子。
11-5-2 DIT 与 DIF 对比 DIT and DIF Comparison
DIT 和 DIF 的运算量相同，都是：
二者的差别主要在数据顺序：
| 算法 Algorithm | 输入顺序 Input Order | 输出顺序 Output Order | 蝶形位置 |
|---|---|---|---|
| DIT FFT | 位反转顺序 | 自然顺序 | 先小 DFT，后合成 |
| DIF FFT | 自然顺序 | 位反转顺序 | 先分解，后小 DFT |
DIF 的流图可以看作 DIT 流图的转置形式。实际程序中选择 DIT 或 DIF，通常取决于数据进入和离开 FFT 模块时更方便采用哪一种顺序。
11-6 用 FFT 计算 IDFT IDFT Using FFT
IDFT 的定义为：
对两边取共轭：
因此：
右侧正好是序列
对应步骤：
- 对频域序列
取共轭； - 对
做一次 FFT； - 对 FFT 输出取共轭；
- 乘以
。
这也是许多库函数中 ifft 可以复用 fft 内核的原因。
11-7 MATLAB 中的 DFT/IDFT MATLAB DFT and IDFT
11-7-1 直接矩阵计算 Matrix Computation
DFT 可以写成矩阵乘法：
其中：
IDFT 对应：
MATLAB 中可以直接构造 DFT 矩阵：
N = length(x);
n = 0:N-1;
k = n.';
W = exp(-1j*2*pi/N);
D = W .^ (k*n);
X = D * x(:);
x_rec = (1/N) * conj(D) * X;这种写法适合验证公式。实际计算不建议用它处理大规模数据，因为矩阵乘法仍然是
11-7-2 fft 与 ifft 函数 fft and ifft
MATLAB 的 DFT 与 IDFT 通常直接使用：
X = fft(x, N);
x_rec = ifft(X, N);若未给出 fft(x) 默认使用 length(x)。若给出更大的
线性卷积也可以通过 FFT 计算。设
对应 MATLAB 写法：
N = length(x) + length(h) - 1;
y = ifft(fft(x, N) .* fft(h, N));补零到更长的
11-8 位反转地址 Bit-Reversed Addressing
radix-2 FFT 的每一级都在二进制索引上分组。若：
则位反转地址为：
以
| 原地址 | 二进制 | 位反转二进制 | 位反转地址 |
|---|---|---|---|
000 | 000 | ||
001 | 100 | ||
010 | 010 | ||
011 | 110 | ||
100 | 001 | ||
101 | 101 | ||
110 | 011 | ||
111 | 111 |
DIT 常把输入预先排成位反转顺序，使输出自然有序；DIF 常保持输入自然有序，使输出落在位反转顺序。硬件或高性能库中通常会用专门的位反转寻址来减少数据搬移。